package org.example;

public class HeapSort {

    public void heapSort(int[] arr) {
        int n = arr.length;

        // 构建最大堆（从最后一个非叶子节点开始调整）
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(arr, n, i);
        }

        // 依次提取堆顶元素（最大值），与末尾元素交换并调整堆
        for (int i = n - 1; i > 0; i--) {
            // 交换堆顶和当前末尾元素
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;

            // 调整剩余元素的堆结构
            heapify(arr, i, 0);
        }
    }

    // 堆调整函数（大顶堆）
    private void heapify(int[] arr, int heapSize, int rootIndex) {
        int largest = rootIndex;   // 初始化最大元素为根节点
        int leftChild = 2 * rootIndex + 1;
        int rightChild = 2 * rootIndex + 2;

        // 如果左子节点大于根节点
        if (leftChild < heapSize && arr[leftChild] > arr[largest]) {
            largest = leftChild;
        }

        // 如果右子节点大于当前最大值
        if (rightChild < heapSize && arr[rightChild] > arr[largest]) {
            largest = rightChild;
        }

        // 如果最大值不是根节点，则交换并递归调整
        if (largest != rootIndex) {
            int swap = arr[rootIndex];
            arr[rootIndex] = arr[largest];
            arr[largest] = swap;

            // 递归调整受影响的子树
            heapify(arr, heapSize, largest);
        }
    }

    // 测试代码
    public static void main(String[] args) {
        int[] arr = {3, 8, 5, 12, 7, 1, 9};
        System.out.println("原始数组：");
        printArray(arr);

        HeapSort sorter = new HeapSort();
        sorter.heapSort(arr);

        System.out.println("\n排序后数组：");
        printArray(arr);
    }

    // 辅助打印方法
    private static void printArray(int[] arr) {
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}